package leetcode.bfs.common;

import javafx.util.Pair;
import leetcode.tree.common.Node;
import leetcode.tree.common.TreeNode;
import leetcode.tree.common.TreeUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;
import java.util.stream.Collectors;

public class BFSUtils {
    private static final Logger logger = LoggerFactory.getLogger(BFSUtils.class);

    public static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            level++;
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                if (curNode.left == null && curNode.right == null) {
                    return level;
                } else {
                    if (curNode.left != null) {
                        queue.add(curNode.left);
                    }
                    if (curNode.right != null) {
                        queue.add(curNode.right);
                    }
                }
            }
        }
        return -1;
    }

    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> valQueue = new LinkedList<>();
        queue.add(root);
        valQueue.add(root.val);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                Integer curSum = valQueue.poll();
                if (curNode.left == null && curNode.right == null) {
                    if (curSum == targetSum) {
                        return true;
                    }
                }
                if (curNode.left != null) {
                    queue.add(curNode.left);
                    valQueue.add(curSum + curNode.left.val);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                    valQueue.add(curSum + curNode.right.val);
                }
            }
        }
        return false;
    }

    public static Node connect(Node root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            root.next = null;
            return root;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                Node curNode = queue.poll();
                if (i == levelSize - 1) {
                    curNode.next = null;
                } else {
                    curNode.next = queue.peek();
                }
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
        }
        return root;
    }

    /**
     * 你只能使用常量级额外空间。
     * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
     *
     * @param root
     * @return
     */
    public static Node connectPro(Node root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            root.next = null;
            return root;
        }
        root.next = null;
        connectNextLevel(root);
        return root;
    }

    public static void connectNextLevel(Node firstNode) {
        if (firstNode == null) {
            return;
        }
        Node curNode = firstNode;
        Node firstNodeOfNextLevel = null;
        while (curNode != null) {
            if (curNode.left == null && curNode.right == null) {
                curNode = curNode.next;
                continue;
            }
            if (firstNodeOfNextLevel == null) {
                if (curNode.right != null) {
                    firstNodeOfNextLevel = curNode.right;
                }
                if (curNode.left != null) {
                    firstNodeOfNextLevel = curNode.left;
                }
            }
            dealRoot(curNode);
            curNode = curNode.next;
        }
        if (firstNodeOfNextLevel == null) {
            return;
        }
        connectNextLevel(firstNodeOfNextLevel);
    }

    private static void dealRoot(Node root) {
        if (root.left != null) {
            if (root.right != null) {
                root.left.next = root.right;
            } else {
                Node nextNode = root.next;
                while (nextNode != null) {
                    if (nextNode.left == null && nextNode.right == null) {
                        nextNode = nextNode.next;
                    } else {
                        break;
                    }
                }
                if (nextNode == null) {
                    root.left.next = null;
                } else {
                    if (nextNode.left != null) {
                        root.left.next = nextNode.left;
                    } else {
                        root.left.next = nextNode.right;
                    }
                }
            }
        }
        if (root.right != null) {
            Node nextNode = root.next;
            while (nextNode != null) {
                if (nextNode.left == null && nextNode.right == null) {
                    nextNode = nextNode.next;
                } else {
                    break;
                }
            }
            if (nextNode == null) {
                root.right.next = null;
            } else {
                if (nextNode.left != null) {
                    root.right.next = nextNode.left;
                } else {
                    root.right.next = nextNode.right;
                }
            }
        }
    }

    public static int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int result = 0;
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            if (curNode.left != null && curNode.left.left == null && curNode.left.right == null) {
                result += curNode.left.val;
            }
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
        return result;
    }

    public static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if (root.children.isEmpty()) {
            List<Integer> curLevel = new ArrayList<>();
            curLevel.add(root.val);
            result.add(curLevel);
            return result;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> curLevel = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                Node curNode = queue.poll();
                curLevel.add(Objects.requireNonNull(curNode).val);
                if (!curNode.children.isEmpty()) {
                    for (int j = 0; j < curNode.children.size(); j++) {
                        if (curNode.children.get(j) != null) {
                            queue.add(curNode.children.get(j));
                        }
                    }
                }
            }
            result.add(curLevel);
        }
        return result;
    }

    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size() > 0) {
            TreeNode curNode = queue.poll();
            TreeNode temp = curNode.left;
            curNode.left = curNode.right;
            curNode.right = temp;
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
        return root;
    }

    public static List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        if (root.left == null && root.right == null) {
            list.add((double) root.val);
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            double levelSum = 0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                if (curNode == null) {
                    continue;
                }
                levelSum += curNode.val;
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            list.add(levelSum / levelSize);
        }
        return list;
    }

    public static TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            if (root.val == val) {
                return root;
            } else {
                return null;
            }
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            if (curNode.val == val) {
                return curNode;
            }
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
        return null;
    }

    public static int minDiffInBST(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> list = new ArrayList<>();
        while (queue.size() > 0) {
            TreeNode curNode = queue.poll();
            list.add(curNode.val);
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
        Collections.sort(list);
        int result = Integer.MAX_VALUE;
        for (int i = 1; i < list.size(); i++) {
            result = Math.min(result, Math.abs(list.get(i) - list.get(i - 1)));
        }
        return result;
    }

    public static boolean isUnivalTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int value = root.val;
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            if (curNode.val != value) {
                return false;
            }
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
        return true;
    }

    public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return null;
        }
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        Queue<TreeNode> queue1 = new LinkedList<>();
        queue1.add(root1);
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue2.add(root2);

        // 将树2往树1上面合并
        root1.val = root1.val + root2.val;

        while (!queue1.isEmpty() || !queue2.isEmpty()) {
            TreeNode curNode1;
            if (queue1.isEmpty()) {
                curNode1 = null;
            } else {
                curNode1 = queue1.poll();
            }
            TreeNode curNode2;
            if (queue2.isEmpty()) {
                curNode2 = null;
            } else {
                curNode2 = queue2.poll();
            }

            if (curNode1 == null) {
                continue;
            }

            if (curNode2 != null) {
                curNode1.left = mergeChild(curNode1.left, curNode2.left);
                curNode1.right = mergeChild(curNode1.right, curNode2.right);
                queue2.add(curNode2.left);
                queue2.add(curNode2.right);
            } else {
                queue2.add(null);
                queue2.add(null);
            }
            queue1.add(curNode1.left);
            queue1.add(curNode1.right);

        }

        return root1;
    }

    private static TreeNode mergeChild(TreeNode child1, TreeNode child2) {
        if (child1 == null && child2 == null) {
            return null;
        }
        if (child1 == null) {
            return new TreeNode(child2.val);
        }
        if (child2 == null) {
            return child1;
        }
        child1.val += child2.val;
        return child1;
    }

    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if (root.left == null && root.right == null) {
            result.add(root.val);
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                if (i == 0) {
                    result.add(curNode.val);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
            }
        }
        return result;
    }

    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count = 0;
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            count++;
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
        }
        return count;
    }

    public static List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if (root.left == null && root.right == null) {
            result.add(root.val);
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int levelMax = Integer.MIN_VALUE;
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                levelMax = Math.max(levelMax, curNode.val);
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            result.add(levelMax);
        }
        return result;
    }

    public static int findBottomLeftValue(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int result = root.val;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                if (i == 0) {
                    result = curNode.val;
                }
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
        }
        return result;
    }

    public static int widthOfBinaryTree(TreeNode root) {
        if (root.left == null && root.right == null) {
            return 1;
        }
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(root, 0));
        int result = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int startIndex = -1;
            int endIndex = -1;
            for (int i = 0; i < levelSize; i++) {
                Pair<TreeNode, Integer> pair = queue.poll();
                Integer index = pair.getValue();
                if (i == 0) {
                    startIndex = index;
                }
                if (i == levelSize - 1) {
                    endIndex = index;
                }
                TreeNode node = pair.getKey();
                if (node.left != null) {
                    queue.add(new Pair<>(node.left, 2 * index));
                }
                if (node.right != null) {
                    queue.add(new Pair<>(node.right, 2 * index + 1));
                }
            }
            result = Math.max(result, endIndex - startIndex + 1);
        }
        return result;
    }

    public static int maxLevelSum(TreeNode root) {
        if (root.left == null && root.right == null) {
            return 1;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // key 为和, value 为层号
        Pair<Integer, Integer> pair = new Pair<>(root.val, 1);
        int level = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int levelSum = 0;
            level++;
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                levelSum += curNode.val;
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            if (levelSum > pair.getKey()) {
                pair = new Pair<>(levelSum, level);
            }
        }
        return pair.getValue();
    }

    public static int deepestLeavesSum(TreeNode root) {
        if (root.left == null && root.right == null) {
            return root.val;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int result = root.val;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int levelSum = 0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                levelSum += curNode.val;
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            result = levelSum;
        }
        return result;
    }

    public static List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = TreeUtils.midTraverse(root1);
        List<Integer> list2 = TreeUtils.midTraverse(root2);
        List<Integer> result = new ArrayList<>();
        if (!list1.isEmpty()) {
            result.addAll(list1);
        }
        if (!list2.isEmpty()) {
            result.addAll(list2);
        }
        return result.stream().sorted().collect(Collectors.toList());
    }

    public static TreeNode getTargetCopy(TreeNode original, TreeNode cloned, TreeNode target) {
        TreeNode root = cloned;
        int targetVal = target.val;
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            if (root.val == targetVal) {
                return root;
            } else {
                return null;
            }
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            if (curNode.val == targetVal) {
                return curNode;
            }
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
        return null;
    }

    public static int minimumOperations(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int result = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                if (curNode == null) {
                    continue;
                }
                list.add(curNode.val);
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            result = getMinOperateTimes(result, list);
        }
        return result;
    }

    private static int getMinOperateTimes(int result, List<Integer> list) {
        Integer[] original = list.toArray(new Integer[0]);
        Collections.sort(list);
        Integer[] sorted = list.toArray(new Integer[0]);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < list.size(); i++) {
            map.put(sorted[i], i);
        }
        // 存在置换环,此处直接暴力交换当前位置上的数到正确的位置上,本质上也是沿着置换环交换元素
        for (int i = 0; i < original.length; i++) {
            // 如果当前位置上放的不是当前位置应该放的数,将当前位置上的数交换到应该在的位置上
            // 直到当前位置出现当前位置应该放的数为止
            while (!Objects.equals(original[i], sorted[i])) {
                // 找到当前数的正确位置
                int rightIndex = map.get(original[i]);
                // 把当前位置上的数放到它正确的位置上
                swap(original, i, rightIndex);
                result++;
            }
        }
        return result;
    }

    private static void swap(Integer[] original, int i, int j) {
        int temp = original[i];
        original[i] = original[j];
        original[j] = temp;
    }

    public static int islandPerimeter(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                    grid[i][j] = 2;
                    break;
                }
            }
            if (queue.size() > 0) {
                break;
            }
        }
        if (queue.isEmpty()) {
            return 0;
        }
        int[] x = {0, 0, 1, -1};
        int[] y = {1, -1, 0, 0};
        int result = 0;
        while (queue.size() > 0) {
            int[] curPos = queue.poll();
            int curX = curPos[0];
            int curY = curPos[1];
            for (int i = 0; i < 4; i++) {
                int newX = curX + x[i];
                int newY = curY + y[i];
                if (newX < 0 || newX >= row || newY < 0 || newY >= col) {
                    result++;
                    continue;
                }
                if (grid[newX][newY] == 2) {
                    continue;
                }
                if (grid[newX][newY] == 1) {
                    queue.add(new int[]{newX, newY});
                    grid[newX][newY] = 2;
                } else {
                    result++;
                }
            }
        }
        return result;
    }

    public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        Queue<int[]> queue = new LinkedList<>();
        int row = image.length;
        int col = image[0].length;
        queue.add(new int[]{sr, sc});
        int sColor = image[sr][sc];
        image[sr][sc] = newColor;
        if (newColor == sColor) {
            return image;
        }
        int[] x = {0, 0, 1, -1};
        int[] y = {1, -1, 0, 0};
        while (queue.size() > 0) {
            int[] curPos = queue.poll();
            int curX = curPos[0];
            int curY = curPos[1];
            for (int i = 0; i < 4; i++) {
                int newX = curX + x[i];
                int newY = curY + y[i];
                if (newX < 0 || newX >= row || newY < 0 || newY >= col) {
                    continue;
                }
                if (image[newX][newY] == sColor) {
                    queue.add(new int[]{newX, newY});
                    image[newX][newY] = newColor;
                }
            }
        }
        return image;
    }

    public static TreeNode replaceValueInTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        Map<Integer, Integer> levelToSumMap = new HashMap<>();
        int level = 0;
        while (queue.size() > 0) {
            int levelSize = queue.size();
            level++;
            int levelSum = 0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                levelSum += curNode.val;
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            levelToSumMap.put(level, levelSum);
        }
        queue.clear();
        queue.add(root);
        level = 0;
        root.val = 0;
        while (queue.size() > 0) {
            int levelSize = queue.size();
            level++;
            for (int i = 0; i < levelSize; i++) {
                TreeNode curNode = queue.poll();
                int childSum = 0;
                if (curNode.left != null) {
                    childSum += curNode.left.val;
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    childSum += curNode.right.val;
                    queue.add(curNode.right);
                }
                int childLevelSum = levelToSumMap.getOrDefault(level + 1, 0);
                if (childSum == childLevelSum) {
                    if (curNode.left != null) {
                        curNode.left.val = 0;
                    }
                    if (curNode.right != null) {
                        curNode.right.val = 0;
                    }
                } else if (childSum < childLevelSum) {
                    if (curNode.left != null) {
                        curNode.left.val = childLevelSum - childSum;
                    }
                    if (curNode.right != null) {
                        curNode.right.val = childLevelSum - childSum;
                    }
                }
            }
        }
        return root;
    }
}
